The OSPF protocol is a protocol of the Transmission Control Protocol/Internet Protocol (TCP/IP) family making it possible for the routing systems or “routers” of an Internet network to have sufficient knowledge of the network to route the received packets correctly to their destinations.
The particularity of the OSPF protocol is that it is a dynamic routing protocol, i.e. it is capable of taking account of changes in the topology of the network in dynamic manner. For this purpose, the protocol has steps in which messages are exchanged periodically, in order to update constantly the knowledge that each router possesses of the network or of a portion of the network.
FIG. 1 shows a possible environment for a router R1. In this example, it is connected to three networks.
It is connected to a network made up of a single router R2 via a point-to-point connection (e.g. a serial link).
It also has a second connection with a network made up of two routers R3 and R4. For example, this network may be of the point-to-multipoint type, of the broadcast type, or of the non-broadcast multiaccess type.
Finally, it has a third connection with a network made up of a set of host stations H1, H2, . . . , Hn. This type of network is known as a “stub network”.
At regular intervals, the router R1 transmits a “hello” message over each of its connections in order to indicate to its neighbors that it is still active. It also receives “hello” messages from its neighbors, also indicating that they are still active.
“Hello” messages are transmitted (i.e. sent out and received) via physical interfaces. In accordance with the OSPF protocol, each router has a physical interface for each connection. In the example shown in FIG. 1, the router R1 therefore has three interfaces, namely IA with the router R2, IB with the routers R3 and R4, and IC with the set of host stations.
Each of the interfaces is managed by a state machine that is dedicated to it. Such a state machine is represented by FIG. 2.
As is conventional, the circles represent the states which the interface can occupy. At any given time, the interface must be in one of these states. Each arrow in the diagram represents a transition from one state to another.
The names of the states are given in the diagram, as they appear in RFC 2328.
The initial state of the state machine is represented by the circle referenced “Down”. In this initial state, the interface does not allow any traffic to pass.
The “InterfaceUp” event indicates that the interface becomes operational, and that the state machine must exit the “Down” state. There are then two possibilities, as a function of the type of connection managed by the interface. When the connection is of the “point-to-point” type with another router (as it is between the routers R1 and R2 in the example shown in FIG. 1), the state machine goes to a state referenced “Point to Point”. Otherwise, the state machine goes to the “Waiting” state.
Using the example shown in FIG. 1, and assuming that the state machines were previously in the “Down” state, the occurrence of an “InterfaceUp” event causes the state machines of the interfaces IC and IB to go to the “Waiting” state, and causes the state machine associated with the Interface IA to go the “Point-to-Point” state.
In this “Waiting” state, the state machine triggers transmission of “Hello” messages to discover the state of the connection. Another object of transmitting such “Hello” messages is to determine the designated router (DR) and the backup designated router.
This concept of “designated router” corresponds to electing a reference router from among a set of routers, the data that the other routers in the set possess about the network being synchronized by those routers on said designated router. This data is stored in each router in a database.
In compliance with the OSPF protocol, each router has routing tables making it possible to route the packets received in an entire region of the network. The routing tables are computed by the routers on the basis of the databases. To ensure that the routing tables are constantly up to date, the routers exchange messages for updating their databases.
In order to reduce the traffic over the network, a designated router is therefore established via which the other routers update their own databases.
This “election” mechanism is described more precisely in the IETF's RFC 2328.
It is important herein merely to note that the “Waiting” state corresponds to a stage of listening to the network in order to determine whether a designated router or a backup designated router already exists.
This state ends with the appearance of a “WaitTimer” event indicating that a predetermined time (typically 40 seconds) has elapsed, or of a “BackupSeen” event indicating that a backup designated router has been detected.
Depending on the result of this election stage, the state machine goes respectively to the “DR” state, to the “Backup” state, or to the “DROther” state.
The “NeighborChange” event occurs when there is a change in the network connected to the physical interface in question that has an impact on the designated router and/or on the backup designated router. This event may trigger a change of state in the state machine.
Finally, the “Loopback” state indicates that the interface is looped back on itself, i.e. it cannot receive messages from outside the router. The state machine goes to this state after a “LoopInd” event. It exits from it by means of the “UnLoopInd” event and goes to the “Down” state.
When a router is re-started, e.g. after a failure, the state machine thus has to re-start in the “Down” state. The other routers in communication with it are then warned of this change, and they can also be subjected to a change of state in their own state machines by triggering a “NeighborChange” event.
In order to minimize the consequences of the router failing or of it being shut down temporarily for maintenance purposes, it is possible to provide for redundancy in the routing function implemented by the routers.
Such redundancy can be achieved by having an active router and a standby router. The standby router becomes active when the active router stops, e.g. due to failure.
Such a solution is, in particular, implemented by Cisco, in the Hot Standby Router Protocol (HSRP).
Another redundancy solution is described in IETF's RFC 2338, entitled “Virtual Router Redundancy Protocol”.
However, in that solution as well, when a first router in the active state fails and causes the standby second router to take over, the state machines managing the interfaces with the various connections of the router in question must re-start in the “Down” state.
That results in the second router being unavailable for a time lapse before it can return to the state in which the first router was before it failed or stopped. That delay is at least as long as the waiting time prior to election, i.e. typically 40 seconds.
Re-starting state machines also suffers from the drawback of causing changes in the states of the neighboring routers.